package buaa.leetcode.Greedy;

public class JumpGame2 {
	public static int jump(int[] A) {
		if(A.length <= 1){return 0;}
		int oldMax = A[0];
		int newMax = A[0];
		int step = 1;
		for(int i = 1; i < A.length ; i++){
			if( oldMax > A.length - 1){
				return step;
			}
			if( oldMax < i){
				oldMax = newMax;
				step++;
				if(oldMax < i){
					return -1;
				}
			}
			newMax = Math.max(newMax, i + A[i]);
		}
		return step;
    }
	public static void main(String[] args) {
		//System.out.println(canJump(new int[]{2,3,1,1,4}));
		//System.out.println(canJump(new int[]{3,2,1,0,4}));
		System.out.println(jump(new int[]{2,3,1,1,4}));
	}

}
